
public class StingPatternMatching {
	
	/**
	 * KMP
	 */
	void KMP(){
		
	}
	static String patternStr = "";
	static int[] borderWidth = null;
	/**
	 * KMP prepreocessing, this is finding longest string prefix which is also a suffix
	 * if str = wx = yw then we need to find w for each prefix, so that we could slide by that
	 * 
	 * ||||| ...........||||| ....... suppose we are here
	 *      w                i
	 * ||||w............|||||i....... if mis match, go on till we find a match or -1 in that case border can't be extended
	 * |||||w'''''''''''||||||i...... if char match, extend the border      
	 */
	static void prefixFunctionForKMP(){
		borderWidth = new int [patternStr.length()+1];
		int w=-1;
		borderWidth[0] = w; //for single char and two char border width is zero
		for(int i=0; i<patternStr.length();){
			while(w>=0 && patternStr.charAt(i) != patternStr.charAt(w)) w= borderWidth[w]; //if mismatch go till we  
			borderWidth[++i] = ++w; //if match increment 
		}
	}
	
	/**
	 * 
	 */
	static String text = "";
	static int KMP_search(){
		int j = 0; //notice j is initialized outside loop
		for(int i=0; i<text.length();){
			while(j>=0 && patternStr.charAt(j) != text.charAt(i)){
				int shift = borderWidth[j]; //if char wont match then we advance by border width
				j = shift;
			}
			j++;i++;
			if(j == patternStr.length()){
				j = borderWidth[j];
				return i- patternStr.length();
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		patternStr = "ababaa";
		text = "aaabaababaab";
		prefixFunctionForKMP();
		System.out.println(KMP_search());
	}

}
